{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Maximum Value in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph #topological-sort #array #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图 #拓扑排序 #数组 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化网格中的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含&nbsp;<strong>不同&nbsp;</strong>正整数的 <code>m × n</code> 整数矩阵 <code>grid</code>。</p>\n",
    "\n",
    "<p>必须将矩阵中的每一个整数替换为正整数，且满足以下条件:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在替换之后，同行或同列中的每两个元素的&nbsp;<strong>相对&nbsp;</strong>顺序应该保持&nbsp;<strong>不变</strong>。</li>\n",
    "\t<li>替换后矩阵中的 <strong>最大</strong> 数目应尽可能 <strong>小</strong>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果对于原始矩阵中的所有元素对，使&nbsp;<code>grid[r<sub>1</sub>][c<sub>1</sub>] &gt; grid[r<sub>2</sub>][c<sub>2</sub>]</code>，其中要么&nbsp;<code>r<sub>1</sub> == r<sub>2</sub></code> ，要么&nbsp;<code>c<sub>1</sub> == c<sub>2</sub></code>，则相对顺序保持不变。那么在替换之后一定满足&nbsp;<code>grid[r<sub>1</sub>][c<sub>1</sub>] &gt; grid[r<sub>2</sub>][c<sub>2</sub>]</code>。</p>\n",
    "\n",
    "<p>例如，如果&nbsp;<code>grid = [[2, 4, 5], [7, 3, 9]]</code>，那么一个好的替换可以是 <code>grid = [[1, 2, 3], [2, 1, 4]]</code> 或 <code>grid = [[1, 2, 3], [3, 1, 4]]</code>。</p>\n",
    "\n",
    "<p>返回&nbsp;<em><strong>结果&nbsp;</strong>矩阵</em>。如果有多个答案，则返回其中&nbsp;<strong>任何&nbsp;</strong>一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/08/09/grid2drawio.png\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[3,1],[2,5]]\n",
    "<strong>输出:</strong> [[2,1],[1,2]]\n",
    "<strong>解释:</strong> 上面的图显示了一个有效的替换。\n",
    "矩阵中的最大值是 2。可以证明，不能得到更小的值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[10]]\n",
    "<strong>输出:</strong> [[1]]\n",
    "<strong>解释:</strong> 我们将矩阵中唯一的数字替换为 1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>grid</code> 由不同的整数组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-maximum-value-in-a-grid](https://leetcode.cn/problems/minimize-maximum-value-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-maximum-value-in-a-grid](https://leetcode.cn/problems/minimize-maximum-value-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,1],[2,5]]', '[[10]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minScore(self, grid: List[List[int]]) -> List[List[int]]:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        # 将所有数字排序\r\n",
    "        nums = []\r\n",
    "        for r in range(m):\r\n",
    "            for c in range(n):\r\n",
    "                nums.append((grid[r][c], r, c))\r\n",
    "        nums.sort()\r\n",
    "\r\n",
    "        # 从最小的数字开始填入，每次更新当前行和列的最大值\r\n",
    "        row_max = [0] * m\r\n",
    "        col_max = [0] * n\r\n",
    "        ans = [[0] * n for _ in range(m)]\r\n",
    "        for num, r, c in nums:\r\n",
    "            ans[r][c] = max(row_max[r], col_max[c]) + 1\r\n",
    "            row_max[r] = ans[r][c]\r\n",
    "            col_max[c] = ans[r][c]\r\n",
    "        return ans\r\n",
    "        \r\n",
    "\r\n",
    "    def minScore2(self, grid: List[List[int]]) -> List[List[int]]:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        hasr, hasc, nhas, ss = [0] * m, [0] * n, [[0] * n for _ in range(m)], sorted([grid[i][j],i,j] for i in range(m) for j in range(n))\r\n",
    "        for v,i,j in ss: hasr[i] = hasc[j] = nhas[i][j] = max(hasr[i], hasc[j]) + 1\r\n",
    "        return nhas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # 将所有数字排序\n",
    "        nums = []\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                nums.append((grid[r][c], r, c))\n",
    "        nums.sort()\n",
    "\n",
    "        # 从最小的数字开始填入，每次更新当前行和列的最大值\n",
    "        row_max = [0] * m\n",
    "        col_max = [0] * n\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for num, r, c in nums:\n",
    "            ans[r][c] = max(row_max[r], col_max[c]) + 1\n",
    "            row_max[r] = ans[r][c]\n",
    "            col_max[c] = ans[r][c]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 将所有数字排序\n",
    "        nums = []\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                nums.append((grid[r][c], r, c))\n",
    "        nums.sort()\n",
    "\n",
    "        # 从最小的数字开始填入，每次更新当前行和列的最大值\n",
    "        row_max = [0] * m\n",
    "        col_max = [0] * n\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for num, r, c in nums:\n",
    "            ans[r][c] = max(row_max[r], col_max[c]) + 1\n",
    "            row_max[r] = ans[r][c]\n",
    "            col_max[c] = ans[r][c]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 将所有数字排序\n",
    "        nums = []\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                nums.append((grid[r][c], r, c))\n",
    "        nums.sort()\n",
    "\n",
    "        # 从最小的数字开始填入，每次更新当前行和列的最大值\n",
    "        row_max = [0] * m\n",
    "        col_max = [0] * n\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for num, r, c in nums:\n",
    "            ans[r][c] = max(row_max[r], col_max[c]) + 1\n",
    "            row_max[r] = ans[r][c]\n",
    "            col_max[c] = ans[r][c]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        \n",
    "        :param grid: \n",
    "        :return: \n",
    "        \"\"\"\n",
    "        ll = []\n",
    "        for k,v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                ll.append((v2, k, k2))\n",
    "        ll.sort(key=lambda x: x[0])\n",
    "        ans = [[0] * len(grid[0]) for _ in range(len(grid))]\n",
    "        row_max = [0] * len(grid)\n",
    "        col_max = [0] * len(grid[0])\n",
    "        for val, h, w in ll:\n",
    "            curv = max(row_max[h], col_max[w]) + 1\n",
    "            ans[h][w] = curv\n",
    "            row_max[h] = curv\n",
    "            col_max[w] = curv\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
